<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: light)">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: dark)"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/hexo/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/hexo/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/hexo/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/hexo/images/logo.svg" color="#222">

<link rel="stylesheet" href="/hexo/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.1/css/all.min.css" integrity="sha256-Z1K5uhUaJXA7Ll0XrZ/0JhX4lAtZFpT6jkKrEDT0drU=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/themes/blue/pace-theme-bounce.css">
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/pace.min.js" integrity="sha256-gqd7YTjg/BtfqWSwsJOvndl0Bxc8gFImLEkXQT8+qj0=" crossorigin="anonymous"></script>

<script class="next-config" data-name="main" type="application/json">{"hostname":"codeleader.gitee.io","root":"/hexo/","images":"/hexo/images","scheme":"Gemini","darkmode":true,"version":"8.14.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":true,"style":"mac"},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":true,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/hexo/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/hexo/js/config.js"></script>

    <meta name="description" content="在蓝桥杯中，算法题目是最容易拉开和竞争者的差距的，接下来我们进行算法方面的学习 一：排序 ​ 在一维数组中，排序是很重要的。下面是三种常用的排序算法：冒泡排序，插入排序，选择排序。">
<meta property="og:type" content="article">
<meta property="og:title" content="蓝桥杯资料">
<meta property="og:url" content="https://codeleader.gitee.io/hexo/2023/03/05/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%B5%84%E6%96%99/index.html">
<meta property="og:site_name" content="CodeLeader">
<meta property="og:description" content="在蓝桥杯中，算法题目是最容易拉开和竞争者的差距的，接下来我们进行算法方面的学习 一：排序 ​ 在一维数组中，排序是很重要的。下面是三种常用的排序算法：冒泡排序，插入排序，选择排序。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://blog.codeleader.top/img/asynccode">
<meta property="og:image" content="http://blog.codeleader.top/img/asynccode">
<meta property="og:image" content="http://blog.codeleader.top/img/asynccode">
<meta property="og:image" content="http://blog.codeleader.top/img/asynccode">
<meta property="og:image" content="http://blog.codeleader.top/img/asynccode">
<meta property="article:published_time" content="2023-03-05T10:38:18.188Z">
<meta property="article:modified_time" content="2023-03-05T10:48:11.552Z">
<meta property="article:author" content="别团等shy哥发育">
<meta property="article:tag" content="蓝桥杯">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://blog.codeleader.top/img/asynccode">


<link rel="canonical" href="https://codeleader.gitee.io/hexo/2023/03/05/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%B5%84%E6%96%99/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://codeleader.gitee.io/hexo/2023/03/05/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%B5%84%E6%96%99/","path":"2023/03/05/蓝桥杯资料/","title":"蓝桥杯资料"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>蓝桥杯资料 | CodeLeader</title>
  








  <noscript>
    <link rel="stylesheet" href="/hexo/css/noscript.css">
  </noscript>
<style>mjx-container[jax="SVG"] {
  direction: ltr;
}

mjx-container[jax="SVG"] > svg {
  overflow: visible;
}

mjx-container[jax="SVG"][display="true"] {
  display: block;
  text-align: center;
  margin: 1em 0;
}

mjx-container[jax="SVG"][justify="left"] {
  text-align: left;
}

mjx-container[jax="SVG"][justify="right"] {
  text-align: right;
}

g[data-mml-node="merror"] > g {
  fill: red;
  stroke: red;
}

g[data-mml-node="merror"] > rect[data-background] {
  fill: yellow;
  stroke: none;
}

g[data-mml-node="mtable"] > line[data-line] {
  stroke-width: 70px;
  fill: none;
}

g[data-mml-node="mtable"] > rect[data-frame] {
  stroke-width: 70px;
  fill: none;
}

g[data-mml-node="mtable"] > .mjx-dashed {
  stroke-dasharray: 140;
}

g[data-mml-node="mtable"] > .mjx-dotted {
  stroke-linecap: round;
  stroke-dasharray: 0,140;
}

g[data-mml-node="mtable"] > svg {
  overflow: visible;
}

[jax="SVG"] mjx-tool {
  display: inline-block;
  position: relative;
  width: 0;
  height: 0;
}

[jax="SVG"] mjx-tool > mjx-tip {
  position: absolute;
  top: 0;
  left: 0;
}

mjx-tool > mjx-tip {
  display: inline-block;
  padding: .2em;
  border: 1px solid #888;
  font-size: 70%;
  background-color: #F8F8F8;
  color: black;
  box-shadow: 2px 2px 5px #AAAAAA;
}

g[data-mml-node="maction"][data-toggle] {
  cursor: pointer;
}

mjx-status {
  display: block;
  position: fixed;
  left: 1em;
  bottom: 1em;
  min-width: 25%;
  padding: .2em .4em;
  border: 1px solid #888;
  font-size: 90%;
  background-color: #F8F8F8;
  color: black;
}

foreignObject[data-mjx-xml] {
  font-family: initial;
  line-height: normal;
  overflow: visible;
}

.MathJax path {
  stroke-width: 3;
}

mjx-container[display="true"] {
  overflow: auto hidden;
}

mjx-container[display="true"] + br {
  display: none;
}
</style></head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/hexo/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">CodeLeader</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">欲买桂花同载酒，终不似少年游</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/hexo/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-about"><a href="/hexo/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li><li class="menu-item menu-item-tags"><a href="/hexo/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签<span class="badge">19</span></a></li><li class="menu-item menu-item-categories"><a href="/hexo/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类<span class="badge">4</span></a></li><li class="menu-item menu-item-archives"><a href="/hexo/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档<span class="badge">17</span></a></li><li class="menu-item menu-item-schedule"><a href="/hexo/schedule/" rel="section"><i class="fa fa-calendar fa-fw"></i>日程表</a></li><li class="menu-item menu-item-sitemap"><a href="/hexo/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a></li><li class="menu-item menu-item-commonweal"><a href="/hexo/404/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>公益 404</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E4%B8%80%E6%8E%92%E5%BA%8F"><span class="nav-number">1.</span> <span class="nav-text">一：排序</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F"><span class="nav-number">1.1.</span> <span class="nav-text">冒泡排序</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F"><span class="nav-number">1.2.</span> <span class="nav-text">选择排序：</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F"><span class="nav-number">1.3.</span> <span class="nav-text">插入排序</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E4%BA%8C%E7%AE%97%E6%B3%95"><span class="nav-number">2.</span> <span class="nav-text">二：算法</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#%E9%80%92%E5%BD%92"><span class="nav-number">2.1.</span> <span class="nav-text">递归</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#%E9%97%AE%E9%A2%98%E9%80%92%E5%BD%92%E5%92%8C%E5%BE%AA%E7%8E%AF%E7%9A%84%E5%85%B3%E7%B3%BB"><span class="nav-number">2.1.1.</span> <span class="nav-text">问题：递归和循环的关系？</span></a></li></ol></li><li class="nav-item nav-level-5"><a class="nav-link" href="#%E5%85%A8%E6%8E%92%E5%88%97"><span class="nav-number">2.2.</span> <span class="nav-text">全排列</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#%E5%9B%9E%E6%BA%AF%E6%B3%95"><span class="nav-number">2.2.1.</span> <span class="nav-text">回溯法</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#%E9%82%BB%E9%87%8C%E4%BA%A4%E6%8D%A2%E6%B3%95"><span class="nav-number">2.2.2.</span> <span class="nav-text">邻里交换法</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE"><span class="nav-number">2.2.3.</span> <span class="nav-text">题目</span></a></li></ol></li><li class="nav-item nav-level-5"><a class="nav-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92dp"><span class="nav-number">2.3.</span> <span class="nav-text">动态规划（DP）</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#%E9%A2%98%E5%9E%8B%E9%9D%92%E8%9B%99%E8%B7%B3%E9%98%B6%E9%97%AE%E9%A2%98"><span class="nav-number">2.3.1.</span> <span class="nav-text">题型：青蛙跳阶问题：</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#%E8%87%AA%E9%A1%B6%E8%80%8C%E4%B8%8B%E6%B1%82%E8%A7%A3"><span class="nav-number">2.3.2.</span> <span class="nav-text">1.自顶而下求解</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#%E8%87%AA%E4%B8%8B%E8%80%8C%E4%B8%8A%E7%9A%84%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="nav-number">2.3.3.</span> <span class="nav-text">2.自下而上的动态规划</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E7%89%B9%E5%BE%81"><span class="nav-number">2.3.4.</span> <span class="nav-text">动态规划的特征：</span></a></li></ol></li><li class="nav-item nav-level-5"><a class="nav-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-number">2.4.</span> <span class="nav-text">动态规划的解题思路</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#bfs%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="nav-number">2.4.1.</span> <span class="nav-text">BFS(广度优先搜索)</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#dfs%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="nav-number">2.4.2.</span> <span class="nav-text">DFS（深度优先搜索）</span></a></li></ol></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="别团等shy哥发育"
      src="https://codeleader.oss-cn-beijing.aliyuncs.com/site/avatar.jpg">
  <p class="site-author-name" itemprop="name">别团等shy哥发育</p>
  <div class="site-description" itemprop="description">别团等shy哥发育的博客</div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/hexo/archives/">
          <span class="site-state-item-count">17</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/hexo/categories/">
        <span class="site-state-item-count">4</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/hexo/tags/">
        <span class="site-state-item-count">19</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/xiongtete0519" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;xiongtete0519" rel="noopener me" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="/hexo/xiongtete0519@gmail.com" title="E-Mail → xiongtete0519@gmail.com" rel="noopener me"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://codeleader.blog.csdn.net/" title="CSDN → https:&#x2F;&#x2F;codeleader.blog.csdn.net&#x2F;" rel="noopener me" target="_blank"><i class="fa CSDN fa-fw"></i>CSDN</a>
      </span>
  </div>

        </div>
      </div>
        <div class="back-to-top animated" role="button" aria-label="返回顶部">
          <i class="fa fa-arrow-up"></i>
          <span>0%</span>
        </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://codeleader.gitee.io/hexo/2023/03/05/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%B5%84%E6%96%99/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://codeleader.oss-cn-beijing.aliyuncs.com/site/avatar.jpg">
      <meta itemprop="name" content="别团等shy哥发育">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="CodeLeader">
      <meta itemprop="description" content="别团等shy哥发育的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="蓝桥杯资料 | CodeLeader">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          蓝桥杯资料
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2023-03-05 18:38:18 / 修改时间：18:48:11" itemprop="dateCreated datePublished" datetime="2023-03-05T18:38:18+08:00">2023-03-05</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/hexo/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
        </span>
    </span>

  
    <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span id="busuanzi_value_page_pv"></span>
    </span>
    <span class="post-meta-break"></span>
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>4.5k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>16 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <p>在蓝桥杯中，算法题目是最容易拉开和竞争者的差距的，接下来我们进行算法方面的学习</p>
<h4 id="一排序"><strong>一：排序</strong></h4>
<p>​ 在一维数组中，排序是很重要的。下面是三种常用的排序算法：冒泡排序，插入排序，选择排序。</p>
<span id="more"></span>
<h5 id="冒泡排序"><strong>冒泡排序</strong></h5>
<blockquote>
<p>原理：比较两个相邻的元素，将较大的值交换到右边</p>
<p>2 8 7 5 9 4 3</p>
<p>第一趟：</p>
<p>​ 第一次：比较第一个和第二个： 2 和 8 ，不需要交换。</p>
<p>​ 第二次：比较 8 和 7， 将8 和7 进行交换： 2 7 8 5 9 4 3</p>
<p>​ 第三次：比较8 和5 ，将8 和5 交换 2 7 5 8 9 4 3</p>
<p>​ 第四次：比较8 和 9 ，不需要交换</p>
<p>​ 第五次：比较9 和 4 ，需要交换 2 7 5 8 4 9 3</p>
<p>​ 第六次：比较9 和3 ，需要交换 <strong>2 7 5 8 4 3 9</strong></p>
<p><strong>第一趟结束后，最大的数字，出现在最后一位</strong></p>
<p>第二趟：</p>
<p>​ 第一次：比较2 和 7 ，不需要交换</p>
<p>​ 第二次：比较7 和5 需要交换： 2 5 7 8 4 3 9</p>
<p>​ 第三次：比较5 和 8 ，不需要交换</p>
<p>​ 第四次：比较8 和4 ，需要交换：2 5 7 4 8 3 9</p>
<p>​ 第五次：比较8 和3 ，需要交换：<strong>2 5 7 4 3 8 9</strong></p>
<p>​ 第六次：比较8 和9，不要交换（？）</p>
<p><strong>第二趟，第二大的数字，出现在倒数第二位</strong></p>
<p>以此类推：第三趟：2 5 4 3 7 8 9 第四趟。。。。。。直到排序完成。</p>
<p>简化：第一趟跑完，最大的数字在最后一位，不用参与排序，第二趟，第二大的 数字在倒数第二位，不用参与排序...</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">题目：排序：[<span class="number">10</span>,<span class="number">1</span>,<span class="number">35</span>,<span class="number">61</span>,<span class="number">89</span>,<span class="number">36</span>,<span class="number">55</span>]</span><br><span class="line"><span class="comment">//外层for循环控制趟，内层控制次</span></span><br><span class="line"><span class="type">int</span> a [] = {<span class="number">10</span>,<span class="number">1</span>,<span class="number">35</span>,<span class="number">61</span>,<span class="number">89</span>,<span class="number">36</span>,<span class="number">55</span>};</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">0</span> ; i &lt; a.length-<span class="number">1</span> ; i++){</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span><span class="number">0</span> ; j&lt; a.length-<span class="number">1</span>-i; j++){</span><br><span class="line">    <span class="keyword">if</span>(a[j]&gt;a[j+<span class="number">1</span>]){<span class="comment">//左边大于右边</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">k</span> <span class="operator">=</span> a[j];</span><br><span class="line">        a[j] = a[j+<span class="number">1</span>];</span><br><span class="line">        a[j+<span class="number">1</span>] =k;</span><br><span class="line">    }</span><br><span class="line">}</span><br><span class="line">}</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">0</span> ; i &lt; a.length ;i++){</span><br><span class="line"> System.out.print(a[i] +<span class="string">" "</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h5 id="选择排序"><strong>选择排序：</strong></h5>
<blockquote>
<p>原理：</p>
<p>​ 第一次：从未排序的数据元素里面，选出一个最小的（最大的）的元素，然后和第一位元素交换位置。</p>
<p>​ 第二次：选出第二小的（第二大的）的元素，然后和第二位元素交换位置。</p>
<p>.........</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> a [] = {<span class="number">2</span>,<span class="number">9</span>,<span class="number">5</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">3</span>,<span class="number">6</span>,<span class="number">8</span>};</span><br><span class="line"><span class="type">int</span> <span class="variable">begin</span> <span class="operator">=</span><span class="number">0</span>;</span><br><span class="line"><span class="type">int</span> <span class="variable">end</span> <span class="operator">=</span> a.length-<span class="number">1</span>;</span><br><span class="line"><span class="keyword">while</span> (begin &lt;end){</span><br><span class="line"> <span class="type">int</span> <span class="variable">min</span> <span class="operator">=</span> a[begin];<span class="comment">//min，用来存储数组中元素的最小值</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">t</span> <span class="operator">=</span> begin;<span class="comment">//t 存储最小值的下标</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> begin; i &lt;=end ; i++){</span><br><span class="line">     <span class="keyword">if</span>(min &gt; a[i]){</span><br><span class="line">         min = a[i];</span><br><span class="line">         t = i;</span><br><span class="line">     }</span><br><span class="line"> }</span><br><span class="line"> a[t] = a[begin];</span><br><span class="line"> a[begin] = min;</span><br><span class="line"> begin++;</span><br><span class="line">}</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">0</span> ; i &lt; a.length ;i++){</span><br><span class="line"> System.out.print(a[i] +<span class="string">" "</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h5 id="插入排序"><strong>插入排序</strong></h5>
<blockquote>
<p>原理：将数列分成两部分：排好序的数列 未排序的数列</p>
<p>在未排序的数列里面。挨个去元素插入到排好序的数列中</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> a [] = {<span class="number">2</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">6</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">7</span>,<span class="number">6</span>,<span class="number">8</span>};</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">1</span> ; i &lt; a.length ; i++){</span><br><span class="line"> <span class="type">int</span> <span class="variable">k</span> <span class="operator">=</span> a[i];<span class="comment">//哨兵。从数组第二位元素开始，每一循环向后移动一位存储元素，</span></span><br><span class="line"> <span class="comment">// 将这个数插入到前面排好序的数列中</span></span><br><span class="line"> <span class="type">int</span> j= i-<span class="number">1</span>;<span class="comment">//排好序的数列中的最后一位</span></span><br><span class="line"> <span class="keyword">while</span> (j &gt;=<span class="number">0</span>&amp;&amp; k&lt;a[j]){<span class="comment">//哨兵要存在左边比它小，右边比它大</span></span><br><span class="line">     a[j+<span class="number">1</span>] = a[j];<span class="comment">//给哨兵的插入腾出位置</span></span><br><span class="line">     j--;<span class="comment">//用j记录哨兵最终插入的位置</span></span><br><span class="line"> }</span><br><span class="line"> a[j+<span class="number">1</span>] = k;<span class="comment">//哨兵插入</span></span><br><span class="line">}</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">0</span> ; i &lt; a.length ;i++){</span><br><span class="line"> System.out.print(a[i] +<span class="string">" "</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h4 id="二算法"><strong>二：算法</strong></h4>
<h5 id="递归"><strong>递归</strong></h5>
<blockquote>
<p>函数/方法 直接/间接 的调用本身。一般用来在数据原来的基础上加减乘除等操作。</p>
<p>案例：斐波那契数列：</p>
<p>​ 1 1 2 3 5 8 13..... 第一个和第二个数字是1，其他的数字等于前两个数字之和。Fn=F(n-1)+F(n-2)</p>
<p>代码：计算第n位的斐波那契数字</p>
<p>//递归：代码简洁，但是涉及到的运算，会随着递归层数的增加成指数级增长。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">Fn</span><span class="params">(<span class="type">int</span> n)</span>{</span><br><span class="line"> <span class="keyword">if</span>(n ==<span class="number">1</span> || n==<span class="number">2</span>){</span><br><span class="line">     <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> Fn(n-<span class="number">1</span>)+Fn(n-<span class="number">2</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<blockquote>
<p>20年Java C组第三题：</p>
<p>如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。</p>
<p>1 2 6 7 15 16 28 29...</p>
<p>3 5 8 14 17 27 30...</p>
<p>4 9 13 18 26 31...</p>
<p>10 12 19 25 32...</p>
<p>11 20 24 33...</p>
<p>21 23 34...</p>
<p>22 35...</p>
<p>容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20行第20列的数是多少？</p>
<ul>
<li>分析：第20行20列处在45度这条线上。</li>
</ul>
<p>​ 这条线上的数字是：1 5 13 25 41 ........两数之差： 4 8 12 16...</p>
<p>​ 每一个都是在前面的基础上+4.可以用递归或者循环。 第n位和n-1位差 (n-1)*4</p>
<p>​ 第20行20列相当于这个数列的第20位数字。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> System.out.println(snack(<span class="number">20</span>));</span><br><span class="line">}</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">snack</span><span class="params">(<span class="type">int</span> n)</span>{</span><br><span class="line"> <span class="keyword">if</span>(n ==<span class="number">1</span>){</span><br><span class="line">     <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> snack(n-<span class="number">1</span>)+<span class="number">4</span>*(n-<span class="number">1</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>任务：找一道排序或者算法（简单的，学过的）相关的题目，写出代码，截图上传文件夹</p>
<h6 id="问题递归和循环的关系">问题：递归和循环的关系？</h6>
<blockquote>
<p>一道题，可以用递归解答，</p>
<ul>
<li>那么可以换成循环解决吗？可以换</li>
<li>代码量变多。运算资源（时间复杂度）</li>
</ul>
<p>如果发现题目用递归运行时间超出限制，那么：</p>
<ul>
<li>换循环</li>
<li>加字典
<ul>
<li>fn(5)= f(4)+f（3） f(4) = f(3)+f(2)[将f(3)和f(2)存起来] f(3)直接得出</li>
</ul></li>
</ul>
</blockquote>
<blockquote>
<p>辗转相除法：求最大公约数</p>
<ul>
<li>两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数（gcd)</li>
<li>gcd(a,b) = gcd(b ,a%b) a&gt;b :当 b的值变成0的时候，a就是要求的最大公约数</li>
<li>案例：12和4的最大公约数 = 4 和 0 4</li>
<li>​ 10 和7 的最大公约数 = 7 和3 = 3 和 1 = 1 和0</li>
</ul>
<p>题目：输入两个数字，求最大公约数？</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//循环解法</span></span><br><span class="line"><span class="type">Scanner</span> <span class="variable">scan</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line"><span class="comment">//a&gt;b  gcd(a,b) = gcd(b ,a%b)  a&gt;b</span></span><br><span class="line"><span class="type">int</span> <span class="variable">a</span> <span class="operator">=</span> scan.nextInt();</span><br><span class="line"><span class="type">int</span> <span class="variable">b</span> <span class="operator">=</span> scan.nextInt();</span><br><span class="line"><span class="keyword">while</span> (b!=<span class="number">0</span>){</span><br><span class="line">   <span class="type">int</span> <span class="variable">c</span> <span class="operator">=</span> a%b;</span><br><span class="line">   a =b;</span><br><span class="line">   b=c;</span><br><span class="line">}</span><br><span class="line">System.out.println(a);</span><br><span class="line"><span class="comment">//递归解法</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line">     <span class="type">Scanner</span> <span class="variable">scanner</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line">     <span class="type">int</span> <span class="variable">a</span> <span class="operator">=</span> scanner.nextInt();</span><br><span class="line">     <span class="type">int</span> <span class="variable">b</span> <span class="operator">=</span> scanner.nextInt();</span><br><span class="line">     <span class="type">int</span> <span class="variable">zz</span> <span class="operator">=</span> zz(a, b);</span><br><span class="line">     System.out.println(zz);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">zz</span><span class="params">(<span class="type">int</span> a,<span class="type">int</span> b)</span>{</span><br><span class="line">     <span class="keyword">if</span>(b==<span class="number">0</span>){</span><br><span class="line">         <span class="keyword">return</span> a;</span><br><span class="line">     }</span><br><span class="line">     <span class="type">int</span> <span class="variable">c</span> <span class="operator">=</span> a%b;</span><br><span class="line">     <span class="keyword">return</span> zz(b,c);</span><br><span class="line"></span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<h5 id="全排列"><strong>全排列</strong></h5>
<ul>
<li>求全排列：全排列指的是：n个元素中取n个元素（全部元素）的所有排列组合情况。</li>
<li>求组合：n个元素，取m个元素(m&lt;=n)的所有组合情况</li>
<li>求子集：n个元素的所有子集（所有的组合情况）</li>
</ul>
<p>全排列常用解决办法：邻里交换法和回溯法</p>
<h6 id="回溯法"><strong>回溯法</strong></h6>
<blockquote>
<p>题目：输入[1,2,3]</p>
<p>输出1,2,3所有的不重复的排列组合：</p>
<p>1 ,2,3 1,3,2</p>
<p>2,1,3 2,3,1</p>
<p>3,1,2 3,2,1</p>
</blockquote>
<p>回溯：一般解决搜索问题，全排列也是一种搜索问题。</p>
<ul>
<li>回溯：就是类似枚举的搜索尝试过程。在搜索过程中寻找问题 的解。当发现不满足求解的条件时，就回溯返回，尝试别的路径。</li>
</ul>
<p>全排列可以使用试探的办法列举所有的可能性。一个长度位n 的序列，所有的排列组合：n!</p>
<blockquote>
<p>1.从集合中选取一个元素（n种情况）,并标记该元素已经被使用。</p>
<p>2.在第一步的基础上递归到下一层，从剩余的n-1 个元素中，按照第一步的方法再找到一个元素，并标记（n-1)</p>
<p>3.依次类推，所有的元素都被标记，将元素存起来，取对比求解的情况。</p>
</blockquote>
<h6 id="邻里交换法"><strong>邻里交换法</strong></h6>
<blockquote>
<p>回溯时试探性填充数据，给每个位置都试探性赋值。</p>
<p>邻里交换，也是通过递归实现，但是是一种基于交换的思路。</p>
<p>步骤：</p>
<ul>
<li>将数组分成2个部分：暂时确定部分和未确定部分。刚开始，都是未确定部分。</li>
<li>在未确定部分中，让每一个数据都有机会和未确定部分中的第一位交换。然后第一位就变成暂时确定部分。</li>
<li>以此类推：每个数据都和未确定部分中的第二位交换（第一位数据除外）.......直到确定所有数据</li>
<li>将确定好的数据和条件对比，对比结束后，还原数据。</li>
</ul>
</blockquote>
<h6 id="题目"><strong>题目</strong></h6>
<blockquote>
<p><strong>2017年Java组c组第三题:</strong></p>
<p>A,2,3,4,5,6,7,8,9共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。 下图就是一种排法。</p>
<p>图片描述这样的排法可能会有很多。</p>
<p>如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？请你计算并提交该数字。</p>
<ul>
<li>分析：同一个三角形，旋转加镜像后会变成6种，所以最终的结果要除6</li>
</ul>
</blockquote>
<p>1.暴力解：</p>
<figure>
<img data-src="http://blog.codeleader.top/img/asynccode" alt=""><figcaption>img</figcaption>
</figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="variable">sum</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">a</span> <span class="operator">=</span> <span class="number">1</span>; a &lt; <span class="number">10</span>; a++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">b</span> <span class="operator">=</span> <span class="number">1</span>; b &lt; <span class="number">10</span>; b++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">c</span> <span class="operator">=</span> <span class="number">1</span>; c &lt; <span class="number">10</span>; c++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">d</span> <span class="operator">=</span> <span class="number">1</span>; d &lt; <span class="number">10</span>; d++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">e</span> <span class="operator">=</span> <span class="number">1</span>; e &lt; <span class="number">10</span>; e++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">f</span> <span class="operator">=</span> <span class="number">1</span>; f &lt; <span class="number">10</span>; f++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">g</span> <span class="operator">=</span> <span class="number">1</span>; g &lt; <span class="number">10</span>; g++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">h</span> <span class="operator">=</span> <span class="number">1</span>; h &lt; <span class="number">10</span>; h++) {</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>; i &lt; <span class="number">10</span>; i++) {</span><br><span class="line"><span class="keyword">if</span>(a==b||a==c||a==d||a==e||a==f||a==g||a==h||a==i</span><br><span class="line">||b==c||b==d||b==e||b==f||b==g||b==h||b==i</span><br><span class="line">||c==d||c==e||c==f||c==g||c==h||c==i</span><br><span class="line">||d==e||d==f||d==g||d==h||d==i</span><br><span class="line">||e==f||e==g||e==h||e==i</span><br><span class="line">||f==g||f==h||f==i</span><br><span class="line">||g==h||g==i</span><br><span class="line">||h==i){</span><br><span class="line"><span class="keyword">continue</span>;</span><br><span class="line">}</span><br><span class="line"><span class="keyword">if</span>(a+b+c+d==d+e+f+g &amp;&amp; d+e+f+g==g+h+i+a){</span><br><span class="line">sum++;</span><br><span class="line">} } } } } } } } } }</span><br><span class="line">System.out.println(<span class="string">"一共有"</span>+sum/<span class="number">6</span>+<span class="string">"种不同的排法"</span>);<span class="comment">//除去镜像和旋转两次，三种重复值为：总数/2/3</span></span><br></pre></td></tr></table></figure>
<p>2.回溯：</p>
<figure>
<img data-src="http://blog.codeleader.top/img/asynccode" alt=""><figcaption>img</figcaption>
</figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="type">int</span> num [] = <span class="keyword">new</span> <span class="title class_">int</span>[<span class="number">10</span>];<span class="comment">//存放数据的数组</span></span><br><span class="line"><span class="keyword">static</span> <span class="type">int</span> count=<span class="number">0</span>;<span class="comment">//符合条件的排列组合个数</span></span><br><span class="line"><span class="keyword">static</span> <span class="type">boolean</span> bool [] = <span class="keyword">new</span> <span class="title class_">boolean</span>[<span class="number">10</span>];</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line">dfs(<span class="number">1</span>);</span><br><span class="line"> System.out.println(count/<span class="number">3</span>/<span class="number">2</span>);<span class="comment">//要除6</span></span><br><span class="line">}</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">dfs</span><span class="params">(<span class="type">int</span> step)</span>{<span class="comment">//初始值为1</span></span><br><span class="line"> <span class="keyword">if</span>(step ==<span class="number">10</span>){<span class="comment">//代表9位数据已经赋值完成  递归的结束条件</span></span><br><span class="line">       <span class="keyword">if</span>(num[<span class="number">1</span>]+num[<span class="number">2</span>]+num[<span class="number">4</span>]+num[<span class="number">6</span>] == num[<span class="number">6</span>]+num[<span class="number">7</span>]+num[<span class="number">8</span>]+num[<span class="number">9</span>] &amp;&amp;</span><br><span class="line">               num[<span class="number">1</span>]+num[<span class="number">2</span>]+num[<span class="number">4</span>]+num[<span class="number">6</span>] == num[<span class="number">1</span>]+ num[<span class="number">3</span>]+ num[<span class="number">5</span>]+ num[<span class="number">9</span>]){</span><br><span class="line">           count++;</span><br><span class="line">       }</span><br><span class="line">       <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">1</span> ; i &lt;<span class="number">10</span> ; i++){</span><br><span class="line">     <span class="keyword">if</span>(!bool[i]){</span><br><span class="line">         bool[i] = <span class="literal">true</span>;<span class="comment">//标记该位数字已赋值</span></span><br><span class="line">         num[step] = i;<span class="comment">//赋值</span></span><br><span class="line">         dfs(step+<span class="number">1</span>);</span><br><span class="line">         bool[i] = <span class="literal">false</span>;<span class="comment">//撤回标记</span></span><br><span class="line">     }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>3.邻里交换法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="type">int</span> count;</span><br><span class="line"> <span class="keyword">static</span> <span class="type">int</span> a [] = {<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">8</span>,<span class="number">9</span>};</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line">  f(a,<span class="number">0</span>);</span><br><span class="line">     System.out.println(count/<span class="number">6</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">f</span><span class="params">(<span class="type">int</span> a[], <span class="type">int</span> step)</span>{</span><br><span class="line">     <span class="keyword">if</span>(step == a.length-<span class="number">1</span>){<span class="comment">//step == 8</span></span><br><span class="line">         <span class="keyword">if</span>(a[<span class="number">0</span>]+a[<span class="number">1</span>]+a[<span class="number">2</span>]+a[<span class="number">3</span>] == a[<span class="number">3</span>]+a[<span class="number">4</span>]+a[<span class="number">5</span>]+a[<span class="number">6</span>]&amp;&amp;</span><br><span class="line">                 a[<span class="number">0</span>]+a[<span class="number">1</span>]+a[<span class="number">2</span>]+a[<span class="number">3</span>]==a[<span class="number">6</span>]+a[<span class="number">7</span>]+a[<span class="number">8</span>]+a[<span class="number">0</span>]){</span><br><span class="line">             count++;</span><br><span class="line">         }</span><br><span class="line">         <span class="keyword">return</span>;</span><br><span class="line">     }</span><br><span class="line"></span><br><span class="line">     <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span>step ; i &lt;a.length; i++){</span><br><span class="line">         {</span><br><span class="line">             <span class="type">int</span> <span class="variable">x</span> <span class="operator">=</span> a[i];<span class="comment">//交换</span></span><br><span class="line">             a[i] = a[step];</span><br><span class="line">             a[step] = x;</span><br><span class="line">         }</span><br><span class="line"></span><br><span class="line">         f(a,step+<span class="number">1</span>);<span class="comment">//递归确定下一位</span></span><br><span class="line">         {</span><br><span class="line">             <span class="type">int</span> <span class="variable">x</span> <span class="operator">=</span> a[i];<span class="comment">//还原</span></span><br><span class="line">             a[i] = a[step];</span><br><span class="line">             a[step] = x;</span><br><span class="line">         }</span><br><span class="line">     }</span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<p>任务：理解全排列-回溯法和全排列-邻里交换法的思路和代码逻辑</p>
<h5 id="动态规划dp"><strong>动态规划（DP）</strong></h5>
<blockquote>
<p>动态规划，常用于：数学，管理科学，计算机科学，经济和生物信息学。</p>
<p>特征：一个问题，可以拆分成一个一个的子问题，解决子问题，顺带解决这个问题</p>
<p>核心思想：拆分子问题，记住过程，减少重复运算。</p>
<p>例子：</p>
<ul>
<li>1+1+1+1+1+1=? 等于6</li>
<li>在上面式子的再加上一个“ 1+”。答案是多少？</li>
<li>直接通过以往计算过的答案，再加1</li>
</ul>
</blockquote>
<h6 id="题型青蛙跳阶问题"><strong>题型：青蛙跳阶问题：</strong></h6>
<h6 id="自顶而下求解"><strong>1.自顶而下求解</strong></h6>
<blockquote>
<p>一只青蛙，可以一次跳上1级台阶，也可以一次跳上2级台阶。求这只青蛙跳10级台阶有多少种跳法？</p>
<p>分析：</p>
<ul>
<li>要跳到第10级台阶，要么从第8级台阶，跳2级到第10级。要么从第9级跳1步到第十级。</li>
<li>要跳到第9级：可以从第8级跳1步到达，也可以从第7级跳两步到达。</li>
<li>要跳到第8级：可以从第7级跳1步到达，也可以从第6级跳两步到达。</li>
<li>............</li>
</ul>
</blockquote>
<p>假设跳到第n 级台阶的跳法是 f(n)，那么：</p>
<blockquote>
<p>f(10) = f(9) + f(8)</p>
<p>f(9) = f(8) + f(7)</p>
<p>f(8) = f(7) + f(6)</p>
<p>......</p>
<p>f(2) = 2:第2级可以一次跳1步，跳两次，也可以一次跳2步</p>
<p>f(1) = 1：只能一次跳1步</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//暴力递归  自顶而下的解</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line"> <span class="type">int</span> <span class="variable">ways</span> <span class="operator">=</span> ways(<span class="number">10</span>);</span><br><span class="line"> System.out.println(<span class="string">"有"</span>+ways+<span class="string">"种跳法"</span>);</span><br><span class="line">}</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">ways</span><span class="params">(<span class="type">int</span> n)</span>{</span><br><span class="line"> <span class="keyword">if</span> (n ==<span class="number">1</span>){</span><br><span class="line">     <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (n ==<span class="number">2</span>){</span><br><span class="line">     <span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> ways(n-<span class="number">1</span>)+ways(n-<span class="number">2</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<ul>
<li>时间复杂度=解决子问题的时间 * 子问题个数 （存在大量重复运算）</li>
<li>改进：通过字典存储子问题的解（数组或者map）</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line">     <span class="type">long</span> <span class="variable">l</span> <span class="operator">=</span> System.currentTimeMillis();</span><br><span class="line">     <span class="type">int</span> <span class="variable">ways</span> <span class="operator">=</span> ways(<span class="number">40</span>);</span><br><span class="line">     <span class="type">long</span> <span class="variable">l1</span> <span class="operator">=</span> System.currentTimeMillis();</span><br><span class="line">     System.out.println(<span class="string">"有"</span>+ways+<span class="string">"种跳法"</span>);</span><br><span class="line">     System.out.println(l1-l);</span><br><span class="line"> }</span><br><span class="line"><span class="keyword">static</span> Map&lt;Integer,Integer&gt; map=  <span class="keyword">new</span> <span class="title class_">HashMap</span>();</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">ways</span><span class="params">(<span class="type">int</span> n)</span>{</span><br><span class="line">     <span class="keyword">if</span> (n ==<span class="number">1</span>){</span><br><span class="line">         <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">     }</span><br><span class="line">     <span class="keyword">if</span> (n ==<span class="number">2</span>){</span><br><span class="line">         <span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">     }</span><br><span class="line">     <span class="keyword">if</span>(map.containsKey(n)){</span><br><span class="line">         <span class="keyword">return</span> map.get(n);</span><br><span class="line">     }<span class="keyword">else</span> {</span><br><span class="line">          map.put(n,(ways(n-<span class="number">1</span>)+ways(n-<span class="number">2</span>)));</span><br><span class="line">         <span class="keyword">return</span> map.get(n);</span><br><span class="line">     }</span><br><span class="line"></span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<h6 id="自下而上的动态规划"><strong>2.自下而上的动态规划</strong></h6>
<p>动态规划和带字典的递归有些不同，但解法类似。都有减少重复运算。</p>
<ul>
<li>带字典的递归是从f(10)---&gt;f(1),自顶而下。</li>
<li>动态规划，从f(1)---&gt;f(10)，自底而上。</li>
</ul>
<h6 id="动态规划的特征"><strong>动态规划的特征：</strong></h6>
<ul>
<li>最优子结构：f(n) = f(n-1) + f(n-2), f(n-1)和 f(n-2)就是f(n)的最优子结构。</li>
<li>状态转移方程：f(n) = f(n-1) + f(n-2)</li>
<li>边界：f(1) =1 ,f(2) = 2</li>
<li>重叠子：重复的运算：f(10) = f(9) + f(8),f(9) = f(8)+f(7). f(8)就是重叠子</li>
</ul>
<figure>
<img data-src="http://blog.codeleader.top/img/asynccode" alt=""><figcaption>img</figcaption>
</figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line">    System.out.println(ways(<span class="number">10</span>));</span><br><span class="line">}</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">ways</span><span class="params">(<span class="type">int</span> n)</span>{</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">1</span>){</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">2</span>){</span><br><span class="line">        <span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">    }</span><br><span class="line">    <span class="comment">//  1    2    1+2    2+3    3+5  5+8</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">a</span> <span class="operator">=</span><span class="number">1</span>; <span class="type">int</span> b=<span class="number">2</span>;  <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span><span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">3</span> ; i&lt;= n; i++){</span><br><span class="line">        temp = a+b;</span><br><span class="line">        a = b;</span><br><span class="line">        b= temp;</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> temp;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h5 id="动态规划的解题思路"><strong>动态规划的解题思路</strong></h5>
<p>什么样的问题适用动态规划？</p>
<blockquote>
<p>如果一个问题，可以把所有的答案穷举出来，而且存在重叠子问题，就可以考虑使用动态规划。</p>
</blockquote>
<p>动态规划的经典应用场景：</p>
<blockquote>
<ul>
<li>最长递增子序列 ---20年蓝肽子问题</li>
<li>最小距离 --- 数字三角形</li>
<li>背包问题</li>
<li>凑零钱问题</li>
<li>等等等。。。</li>
</ul>
</blockquote>
<p>动态规划的解题思路</p>
<ul>
<li>核心思想：拆分子问题，记住过程，减少重叠子运算</li>
<li>穷举分析</li>
<li>确定边界</li>
<li>找出规律，确定最优子结构</li>
<li>写出状态转移方程</li>
<li>代码实现</li>
</ul>
<h6 id="bfs广度优先搜索"><strong>BFS(广度优先搜索)</strong></h6>
<p>2020年数字三角形</p>
<blockquote>
<figure>
<img data-src="http://blog.codeleader.top/img/asynccode" alt=""><figcaption>img</figcaption>
</figure>
<p>上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。</p>
<p>路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。（先行忽略）</p>
<p>输入描述:输入的第一行包含一个整数(1≤N≤100)，表示三角形的行数。下面的N行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。</p>
<p>输入输出样例</p>
<p>5</p>
<p>7</p>
<p>3 8</p>
<p>8 1 0</p>
<p>2 7 4 4</p>
<p>4 5 2 6 5</p>
<p>27</p>
</blockquote>
<blockquote>
<p>忽略条件分析：</p>
<ul>
<li>向左下走的次数与向右下走的次数相差不能超过 1。（先行忽略）</li>
<li>第一行1个数字，第二行2个数字.....</li>
<li>一次走一层：
<ul>
<li>从下往上走：从第四层开始看：第四层的数字判断第五层左下和右下数字谁大，谁大，就加上谁，意味这从下面一层较大的数字走到第4层的这个数字。注意，要记住相加之后的数字！</li>
</ul></li>
<li>//向左下走的次数与向右下走的次数相差不能超过 1。（先行忽略）</li>
</ul>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">Scanner</span> <span class="variable">scanner</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line">System.out.println(<span class="string">"请输入行数"</span>);</span><br><span class="line"><span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> scanner.nextInt();</span><br><span class="line"><span class="type">int</span> [][] array = <span class="keyword">new</span> <span class="title class_">int</span>[n][n];</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span><span class="number">0</span> ;i&lt;n;i++){  <span class="comment">//将数字三角形放入二维数组</span></span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span><span class="number">0</span>; j &lt;=i ; j++){<span class="comment">//控制第几行有几个数字</span></span><br><span class="line">    array[i][j] = scanner.nextInt();</span><br><span class="line">}</span><br><span class="line">}</span><br><span class="line"><span class="comment">//从下到上</span></span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> n-<span class="number">1</span>; i &gt; <span class="number">0</span> ; i--){</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span> ; j &lt;i ; j++){</span><br><span class="line">    <span class="comment">//某个数字（i,j)的左下是（i+1,j),右下是（i+1,j+1)</span></span><br><span class="line">    array[i-<span class="number">1</span>][j] += array[i][j] &gt; array[i][j+<span class="number">1</span>] ? array[i][j] : array[i][j+<span class="number">1</span>];</span><br><span class="line">}</span><br><span class="line">}</span><br><span class="line">System.out.println(array[<span class="number">0</span>][<span class="number">0</span>]);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 从上到下，和从下到上思路类似。</span></span><br></pre></td></tr></table></figure>
<blockquote>
<p>加上条件之后的分析：</p>
<ul>
<li>向左下走的次数与向右下走的次数相差不能超过 1。</li>
<li>如果是奇数行，最终肯定走到最后一行中间的数字。</li>
<li>如果是偶数行，最后肯定是中间的两个数字。</li>
<li></li>
</ul>
<figure>
<img data-src="http://blog.codeleader.top/img/asynccode" alt=""><figcaption>img</figcaption>
</figure>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"> <span class="type">Scanner</span> <span class="variable">scan</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line"><span class="type">int</span> <span class="variable">N</span> <span class="operator">=</span> scan.nextInt();</span><br><span class="line"><span class="type">int</span>[][] arr = <span class="keyword">new</span> <span class="title class_">int</span>[N + <span class="number">1</span>][N + <span class="number">1</span>];</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>; i &lt; N + <span class="number">1</span>; i++) {     <span class="comment">//最左行，最上列为0</span></span><br><span class="line">   <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">1</span>; j &lt; i + <span class="number">1</span>; j++) {</span><br><span class="line">       arr[i][j] = scan.nextInt();</span><br><span class="line">       arr[i][j] += Math.max(arr[i - <span class="number">1</span>][j], arr[i - <span class="number">1</span>][j - <span class="number">1</span>]);</span><br><span class="line">   }</span><br><span class="line">}</span><br><span class="line">scan.close();</span><br><span class="line"><span class="comment">//关键点：若左右移动差值为1，那么一定在中间位置</span></span><br><span class="line"><span class="type">int</span> <span class="variable">res</span> <span class="operator">=</span> (N % <span class="number">2</span> == <span class="number">0</span>) ? Math.max(arr[N][N/<span class="number">2</span>], arr[N][N/<span class="number">2</span>+<span class="number">1</span>]) : arr[N][N/<span class="number">2</span>+<span class="number">1</span>];</span><br><span class="line">System.out.println(res);</span><br></pre></td></tr></table></figure>
<h6 id="dfs深度优先搜索"><strong>DFS（深度优先搜索）</strong></h6>
<blockquote>
<p>2020年国赛:蓝肽子序列(DFS算法)(最长增长子序列) 作业</p>
</blockquote>
<p>本质是：最长增长子序列</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> {</span><br><span class="line">        <span class="type">Scanner</span> <span class="variable">sc</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line">        <span class="type">String</span> <span class="variable">s1</span> <span class="operator">=</span> sc.nextLine();</span><br><span class="line">        <span class="type">String</span> <span class="variable">s2</span> <span class="operator">=</span> sc.nextLine();</span><br><span class="line">        <span class="type">int</span> <span class="variable">n1</span> <span class="operator">=</span> s1.length();</span><br><span class="line">        <span class="type">int</span> <span class="variable">n2</span> <span class="operator">=</span> s2.length();</span><br><span class="line">        <span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span> <span class="variable">m</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span>[] flags1 = <span class="keyword">new</span> <span class="title class_">int</span>[n1+<span class="number">1</span>];</span><br><span class="line">        <span class="type">int</span> <span class="variable">cnt</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>;i&lt;n1;i++){</span><br><span class="line">            <span class="keyword">if</span>(Character.isUpperCase(s1.charAt(i))){</span><br><span class="line">                n++;</span><br><span class="line">                flags1[cnt++] = i;</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">        flags1[cnt] = n1;</span><br><span class="line">        cnt = <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span>[] flags2 = <span class="keyword">new</span> <span class="title class_">int</span>[n2+<span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>;i&lt;n2;i++){</span><br><span class="line">            <span class="keyword">if</span>(Character.isUpperCase(s2.charAt(i))){</span><br><span class="line">                m++;</span><br><span class="line">                flags2[cnt++] = i;</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">        flags2[cnt] = n2;</span><br><span class="line">        <span class="type">int</span>[][] dp = <span class="keyword">new</span> <span class="title class_">int</span>[n+<span class="number">1</span>][m+<span class="number">1</span>];</span><br><span class="line">        <span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>;i&lt;=n;i++){</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">1</span>;j&lt;=m;j++){</span><br><span class="line">                <span class="keyword">if</span>(s1.substring(flags1[i-<span class="number">1</span>],flags1[i]).equals(s2.substring(flags2[j-<span class="number">1</span>],flags2[j]))){</span><br><span class="line">                    dp[i][j] = Math.max(dp[i][j],dp[i-<span class="number">1</span>][j-<span class="number">1</span>]+<span class="number">1</span>);</span><br><span class="line">                }<span class="keyword">else</span>{</span><br><span class="line">                    dp[i][j] = Math.max(dp[i-<span class="number">1</span>][j],dp[i][j-<span class="number">1</span>]);</span><br><span class="line">                }</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">        System.out.println(dp[n][m]);</span><br><span class="line">    }</span><br></pre></td></tr></table></figure>
<p>相信大家已经基本掌握了和竞争者的拉分利器:算法 了，撒花！</p>

    </div>

    
    
    

    <footer class="post-footer">
          

<div class="post-copyright">
<ul>
  <li class="post-copyright-author">
      <strong>本文作者： </strong>别团等shy哥发育
  </li>
  <li class="post-copyright-link">
      <strong>本文链接：</strong>
      <a href="https://codeleader.gitee.io/hexo/2023/03/05/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%B5%84%E6%96%99/" title="蓝桥杯资料">https://codeleader.gitee.io/hexo/2023/03/05/蓝桥杯资料/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

          <div class="post-tags">
              <a href="/hexo/tags/%E8%93%9D%E6%A1%A5%E6%9D%AF/" rel="tag"># 蓝桥杯</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/hexo/2023/03/01/AHP_EW/" rel="prev" title="熵权法">
                  <i class="fa fa-chevron-left"></i> 熵权法
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/hexo/2023/03/07/%E8%93%9D%E6%A1%A5%E6%9D%AF-%E6%9C%80%E4%BC%98%E6%B8%85%E9%9B%B6%E6%96%B9%E6%A1%88/" rel="next" title="蓝桥杯-最优清零方案">
                  蓝桥杯-最优清零方案 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 2022 – 
  <span itemprop="copyrightYear">2024</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">别团等shy哥发育</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
    <span title="站点总字数">81k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:56</span>
  </span>
</div>
<div class="busuanzi-count">
    <span class="post-meta-item" id="busuanzi_container_site_uv">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-item" id="busuanzi_container_site_pv">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>

<!-- <br /> -->
<!-- 网站运行时间的设置 -->
<span id="timeDate">载入天数...</span>
<!-- <span id="times">载入时分秒...</span> -->
<script>
    var now = new Date();
    function createtime() {
        var grt= new Date("11/17/2022 8:00:00");//此处修改你的建站时间或者网站上线时间
        now.setTime(now.getTime()+250);
        days = (now - grt ) / 1000 / 60 / 60 / 24; dnum = Math.floor(days);
        hours = (now - grt ) / 1000 / 60 / 60 - (24 * dnum); hnum = Math.floor(hours);
        if(String(hnum).length ==1 ){hnum = "0" + hnum;} minutes = (now - grt ) / 1000 /60 - (24 * 60 * dnum) - (60 * hnum);
        mnum = Math.floor(minutes); if(String(mnum).length ==1 ){mnum = "0" + mnum;}
        seconds = (now - grt ) / 1000 - (24 * 60 * 60 * dnum) - (60 * 60 * hnum) - (60 * mnum);
        snum = Math.round(seconds); 
        if(String(snum).length ==1 ){snum = "0" + snum;}
        // var times = document.getElementById("times").innerHTML = hnum + " 小时 " + mnum + " 分 " + snum + " 秒";
        document.getElementById("timeDate").innerHTML = "本站已安全运行 "+dnum+" 天 "+hnum + " 小时 " + mnum + " 分 " + snum + " 秒";
    }
setInterval("createtime()",250);
</script>

    </div>
  </footer>

  

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/lozad.js/1.16.0/lozad.min.js" integrity="sha256-mOFREFhqmHeQbXpK2lp4nA3qooVgACfh88fpJftLBbc=" crossorigin="anonymous"></script>
<script src="/hexo/js/comments.js"></script><script src="/hexo/js/utils.js"></script><script src="/hexo/js/motion.js"></script><script src="/hexo/js/next-boot.js"></script>

  <script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.1/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/hexo/js/third-party/search/local-search.js"></script>




  <script src="/hexo/js/third-party/pace.js"></script>

  
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>




  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.2/es5/tex-mml-chtml.js","integrity":"sha256-MASABpB4tYktI2Oitl4t+78w/lyA+D7b/s9GEP0JOGI="}}</script>
<script src="/hexo/js/third-party/math/mathjax.js"></script>



</body>
</html>
